/**
 *升序
 */
public class InsertSort {
    public static void insertSort(int[] array){
        for(int i=1;i< array.length;i++){

            //挖坑--保存数据
            int insertVal=array[i];
            int insertFront=i-1;

             // 找到应该插入的位置&位置数据右移
            for (;insertFront>=0;insertFront--) {
                if (array[insertFront] > insertVal) {
                    array[insertFront + 1] = array[insertFront];
                } else
                    break;
            }
            //因为之前--后退出，所以加回去
            array[insertFront+1]=insertVal;
        }
    }

    public static void main(String[] args) {
        int[] array1={0,5,9,7,8,3,1,2,6,4};
        insertSort(array1);
        for (int x:
             array1) {
            System.out.println(x);
        }
    }
}
